Tính qua ước số chung lớn nhất

Công thức dưới đây chuyển từ việc tính bội số chung nhỏ nhất sang tính ước số chung lớn nhất (GCD):

BCNN ⁡ ( a , b ) = | a ⋅ b | UCLN ⁡ ( a , b ) . {\displaystyle \operatorname {BCNN} (a,b)={\frac {|a\cdot b|}{\operatorname {UCLN} (a,b)}}.}

Có một thuật toán nhanh để tìm GCD mà không yêu cầu phân tích ra thừa số nguyên tố, đó là thuật toán Euclid.Ví dụ:

BCNN ⁡ ( 21 , 6 ) = 21 ⋅ 6 UCLN ⁡ ( 21 , 6 ) = 21 ⋅ 6 3 = 126 3 = 42. {\displaystyle \operatorname {BCNN} (21,6)={21\cdot 6 \over \operatorname {UCLN} (21,6)}={21\cdot 6 \over 3}={126 \over 3}=42.}

Bởi GCD(a, b) là ước số của cả a và b, nên sẽ thuật lợi hơn nếu tính LCM bằng cách chia trước khi nhân:

BCNN ⁡ ( a , b ) = ( | a | UCLN ⁡ ( a , b ) ) ⋅ | b | = ( | b | UCLN ⁡ ( a , b ) ) ⋅ | a | . {\displaystyle \operatorname {BCNN} (a,b)=\left({|a| \over \operatorname {UCLN} (a,b)}\right)\cdot |b|=\left({|b| \over \operatorname {UCLN} (a,b)}\right)\cdot |a|.}

Điều này làm giảm kích thước đầu vào, giảm bộ nhớ cho các giá trị trung gian

BCNN ⁡ ( 21 , 6 ) = 21 UCLN ⁡ ( 21 , 6 ) ⋅ 6 = 21 3 ⋅ 6 = 7 ⋅ 6 = 42. {\displaystyle \operatorname {BCNN} (21,6)={21 \over \operatorname {UCLN} (21,6)}\cdot 6={21 \over 3}\cdot 6=7\cdot 6=42.}

Tìm bội chung nhỏ nhất bằng cách phân tích ra thừa số nguyên tố

Định lý cơ bản của số học nói rằng mọi số nguyên dương lớn hơn 1 có thể biểu diễn một cách duy nhất dạng tích các số nguyên tố (nếu không kể đến thứ tự của các thừa số). Như vậy các hợp số có thể coi như là các nguyên tố cấu thành hợp số.

Ví dụ:

90 = 2 1 ⋅ 3 2 ⋅ 5 1 = 2 ⋅ 3 ⋅ 3 ⋅ 5. {\displaystyle 90=2^{1}\cdot 3^{2}\cdot 5^{1}=2\cdot 3\cdot 3\cdot 5.\,\!}

Ở đây chúng ta có hợp số 90 tạo thành bởi một nguyên tử 2, hai nguyên tử 3 và một nguyên tử 5.

Kiến thức này có thể giúp chúng ta tìm BCNN của một tập hợp các số.

Ví dụ: Tìm giá trị của BCNN(8,9,21).

Đầu tiên, ta phân tích từng số thành dạng tích lũy thừa các số nguyên tố.

8 = 2 3 {\displaystyle 8\;\,\;\,=2^{3}} 9 = 3 2 {\displaystyle 9\;\,\;\,=3^{2}} 21 = 3 ⋅ 7 {\displaystyle 21\;\,=3\cdot 7}

Với mỗi số nguyên tố, chọn lũy thừa cao nhất, tích của chúng cho ta giá trị BCNN cần tìm. bốn thừa số nguyên tố 2, 3, 5 và 7, có bậc cao nhất lần lượt là 23, 32, 50, và 71. Do đó,

BCNN ⁡ ( 8 , 9 , 21 ) = 2 3 ⋅ 3 2 ⋅ 5 0 ⋅ 7 1 = 8 ⋅ 9 ⋅ 1 ⋅ 7 = 504. {\displaystyle \operatorname {BCNN} (8,9,21)=2^{3}\cdot 3^{2}\cdot 5^{0}\cdot 7^{1}=8\cdot 9\cdot 1\cdot 7=504.\,\!}

Thuật toán không thực sự hiệu quả bằng cách rút từ ước chung lớn nhất, bởi chưa có thuật toán hiệu quả để phân tích số nguyên, nhưng nó hiệu quả trong việc minh họa khái niệm.